This invention is in the field of compressed video signal encoders; it pertains to selecting a motion compensation vector by computing the Sum Squared Error, using residue arithmetic.
Video compression is a technique used to send or store digitized video more compactly, so that more "movies" can pass along the same communication channel or be stored in a particular storage medium.
The Motion Pictures Experts Group (MPEG) has defined International Organization for Standardization (ISO) standards for video and audio compression. MPEG-1 is a compression technique for compact disks, and it suited for hard disks. MPEG-2 is a similar compression technique for cable TV and for high definition TV (HDTV). The specific video protocols and specifications for MPEG-1 are defined in a three-part document published in 1993 by ISO and the International Electrotechnical Commission as an international standard, No. ISO/IEC DIS 11172-1, -2, and -3. The specific video protocols and specifications for MPEG-2 are defined in a three-part document published in 1994 by ISO and the International Electrotechnical Commission as a draft international standard, No. ISO/IEC DIS 13818-1,-2, and -3.
However, the terms MPEG-1 and -2 really define only the compressed bitstream--as it is stored or sent, as a communications protocol. Special cases of each fully define the computational effort needed in encoding and decoding these signals by specifying the screen sizes and other parameters. For one special case of MPEG-1, known by the acronym, SIF/CPB, the video's display dimensions are 352 by 240, about half the width and height of a TV screen. MPEG-1 SIF/CPB is currently an established compression technique as large numbers of CD-ROMs are being developed for personal computer multimedia systems. For a special case of MPEG-2, known as main level, the video's display dimensions are 720 by 480, about the width and height of a TV screen. Digital satellite T.V. uses MPEG-2 main level compression technique. For another special case of MPEG-2, known as high level, the video's display dimensions are 1920 by 1080 pixels, a little over twice the height and twice the width of a conventional TV screen. HDTV is expected to use the high level, MPEG-2 compression technique.
In any system meeting MPEG ISO standards, an encoder 102 (see FIG. 1) converts normal video 100 to compressed video and converts normal audio 101 to compressed audio. The combined and compressed signal is sent over a communication channel or stored in a storage medium, either of which is identified in FIG. 1 as data stream 104. Decoder 105 recovers normal video 107 from compressed video data and normal audio 108 from compressed audio data. The invention consists of a circuit that can operate on video signals as part of encoder 102.
The encoder 102 inputs video data from input 100, compresses this data by performing certain operations described below, and sends compressed data in stream 104 (see FIG. 2). A "block" is an 8 by 8 array of adjacent pixels. Video data from input 100 is processed block-by-block. For each input block the encoder 102 actually sends a difference block determined by motion compensation encoding.
For motion compensation encoding, previously sent video data is stored in a memory 103 by the encoder 102 and also in a memory 106 by the decoder 105. The difference block 120 is created in a motion compensation transform encoder 119, pixel-by-pixel, by subtracting from the pixel value of the block of input data 100 the corresponding pixel value of some previously sent reference block read from memory 103. The reference block is identified by motion compensation vector 118, which is a pair of numbers, a horizontal offset and a vertical offset, giving the relative screen offset from each pixel in the input block to the corresponding pixel in the reference block.
In the encoder 102 this difference block 120 is discrete cosine transformed 121 to convert space-domain data to frequency-domain data 122, and is Huffman encoded 123, to send the more common patterns using shorter code words. The encoded video data including the motion compensation vector is sent to the decoder in stream 104. The decoder 105 Huffman decodes the input data from data stream 104, discrete cosine transforms it, to convert frequency-domain data back to space-domain data to recreate the difference block.
Then in the decoder 105, motion compensation decoding adds, pixel-by-pixel, the pixels of the difference block to previously sent pixels stored in 106, which are selected by the motion compensation vector sent through stream 104, to obtain a block of video data to be outputted 107.
In an MPEG motion compensation encoder, theoretically all blocks of previously sent video data should be tested to obtain the motion compensation vector that reduces data rate in the stream 104 to a minimum. Simplistically, a block should be selected that is where the object appeared last, due to motion, because the difference to be sent should be a block of zeros. This motion compensation vector is conceptually an indication of the movement or motion of the input block. However, the motion compensation vector may select a reference block that just happens to result in a lower data rate in data stream 104 by some accident unrelated to the motion of the block of pixels. The motion compensation coding problem really just involves testing previously sent blocks of pixel data to see which previously sent block happens to give the lowest data rate in data stream 104. However, for MPEG-1 SIF/CPB having 352 by 240 pixels, the (352/8=44) by (240/8=30) blocks would each have to be compared to (352-8) by (240-8) test blocks, requiring 44.multidot.30.multidot.340.multidot.232 tests each 1/30 of a second. These &gt;1030 tests per second are beyond the capabilities of a practical low-cost system. Rather, in this preferred embodiment, motion compensation vectors for test blocks are restricted within a range +7 to -8 pixels in the horizontal and vertical direction. The selection of a block should be based on the size of the resulting bit pattern actually generated in stream 104. Rather than completing this encoding of the block, the mean squared error (actually the sum squared error, which is monotonic with mean squared error) of the current block and tested block is computed because the test block with least mean squared error generally produces a small amount of Huffman encoded data to be sent over the stream 104.
To accomplish motion compensation encoding in 102, for each block of input data copied into static RAM 111, a reference block is selected, and its motion compensation vector determined, by testing a large number of blocks of previously sent video data, which have been copied into static RAM 110, against the block of input data. In each test, a test block of previously send video data is selected by addressing SRAM 110 and by controlling barrel switch 112. In the sum squared error circuit 115, each pixel of the block of input data 100 is subtracted from the corresponding pixel of the selected test block, and the difference is squared. The sum of these squares is outputted as the sum squared error 116 of the input block and the test block. Minimum circuit 117 obtains the least sum squared error for each test block and the motion compensation vector 118 thereof.
Integrated circuits implementing MPEG-1 SIF/CPB encoders have been announced at this time, but are very expensive. No integrated circuit implementing high level MPEG-2 has been announced at this time. As with any integrated circuit, the circuit area impacts the cost of the circuit dramatically, and the feasibility of implementing larger circuits. In view of the foregoing, there is a continuing desire in the art for an integrated circuit that can operate as an MPEG encoder that can use less circuit area, and consequently achieve a lower manufacturing cost, than known implementations.
The main problem in encoding an MPEG-1 or MPEG-2 video signal is in determining the motion compensation vector by calculation of a sum squared error. It is an object of the invention to create a circuit in the video encoding circuitry that can efficiently perform a sum squared error calculation, to implement the MPEG-1 or MPEG-2 encoding without undue circuit sizes.
It is another object of the invention to create a sum squared error calculation circuit in a video encoder circuit that operates using residue arithmetic.
It is another object of the invention to implement an efficient residue-to-binary converter.